package com.yulongtian.weekCompetition.month202212.week2;

import java.util.*;

/**
 * 81/109
 *
 * @author yulongTian
 * @create 2022-12-11 11:05
 */
public class Test13 {
    public static void main(String[] args) {
        Allocator allocator = new Allocator(50);

        int[][] orders = {{12, 6}, {28, 16}, {17, 23}, {50, 23}, {6}, {10}, {10}, {16, 8}, {17, 41}, {44, 27}, {12, 45}, {33}, {8}, {16}, {23}, {23}, {23}, {29}, {38, 32}, {29}, {6}, {40, 11}, {16}, {22, 33}, {27, 5}, {3}, {10}, {29}, {16, 14}, {46, 47}, {48, 9}, {36, 17}, {33}, {14, 24}, {16}, {8}, {2, 50}, {31, 36}, {17, 45}, {46, 31}, {2, 6}, {16, 2}, {39, 30}, {33}, {45}, {30}, {27}};

        int i = 1;
        for (int[] order : orders) {
            System.out.print(i++ + " -> ");
            if (i == 45) {
                System.out.println();
            }
            if (order.length == 1) {
                System.out.println(allocator.free(order[0]));
            } else {
                System.out.println(allocator.allocate(order[0], order[1]));
            }
        }


    }


}

class Allocator {

    //连续内存
    private int[] array;

    //内存长度
    private int len;

    //mid列表
    private List<Integer> mIds;

    //开始的索引,连续空闲长度
    private HashMap<Integer, Integer> myMap;

    public Allocator(int n) {
        this.array = new int[n];
        this.mIds = new ArrayList<>();
        this.myMap = new HashMap<>();
        this.len = n;
        myMap.put(0, n);
    }

    public int allocate(int size, int mID) {

        Set<Integer> keySet = myMap.keySet();
        Integer[] keys = new Integer[keySet.size()];
        int temp = 0;
        for (Integer integer : keySet) {
            keys[temp++] = integer;
        }

        //排序
        Arrays.sort(keys);
        boolean flag = false;//是否有这样的空间
        int firstIndex = 0;
        for (Integer key : keys) {
            Integer space = myMap.get(key);

            if (space >= size) {
                //有这样的空间
                flag = true;
                firstIndex = key;
                this.mIds.add(mID);
                for (int i = key; i < key + size; i++) {
                    this.array[i] = mID;
                }
                //整理myMap
                myMap.remove(key);
                myMap.put(key + size, space - size);
                break;
            }
        }

        if (flag) {
            return firstIndex;
        } else {
            return -1;
        }
    }

    public int free(int mID) {
        //不存在
        if (!this.mIds.contains(mID)) {
            return 0;
        }

        //存在

        this.mIds.remove((int) this.mIds.indexOf(mID));

        //结果
        int res = 0;

        //是否结束
        boolean flag = false;

        while (!flag) {
            flag = true;
            //找出在内存中的范围  全闭
            int startIndex = 0;
            int endIndex = 0;
            for (int i = 0; i < this.len; i++) {
                if (this.array[i] == mID) {
                    flag = false;
                    startIndex = i;
                    this.array[i] = 0;
                    while (i + 1 < this.len && this.array[i + 1] == mID) {
                        i++;
                        this.array[i] = 0;
                    }
                    endIndex = i;
                    break;
                }
            }

            if (!flag) {
                //判断是否会连在一起
                if (endIndex + 1 < this.len) {
                    if (myMap.containsKey(endIndex + 1)) {
                        Integer next = myMap.get(endIndex + 1);
                        //有
                        if (next > 0) {
                            myMap.remove(endIndex + 1);
                            myMap.put(startIndex, endIndex - startIndex + next + 1);
                        } else {
                            //没有
                            myMap.remove(endIndex + 1);
                        }
                    }else{
                        myMap.put(startIndex, endIndex - startIndex + 1);
                    }
                } else {
                    myMap.put(startIndex, endIndex - startIndex + 1);
                }
                res += endIndex - startIndex + 1;
            }
        }
        return res;
    }
}

/**
 * Your Allocator object will be instantiated and called as such:
 * Allocator obj = new Allocator(n);
 * int param_1 = obj.allocate(size,mID);
 * int param_2 = obj.free(mID);
 */
